home *** CD-ROM | disk | FTP | other *** search
/ IRIX 6.2 Development Libraries / SGI IRIX 6.2 Development Libraries.iso / dist / complib.idb / usr / share / catman / p_man / cat3 / complib / fft2d.z / fft2d
Text File  |  1996-03-14  |  7KB  |  133 lines
  1.  
  2.  
  3.  
  4. ccccfffffffftttt2222dddd,,,,zzzzfffffffftttt2222dddd((((3333FFFF))))                                            ccccfffffffftttt2222dddd,,,,zzzzfffffffftttt2222dddd((((3333FFFF))))
  5.  
  6.  
  7.  
  8. NNNNAAAAMMMMEEEE
  9.      ccccfffffffftttt2222dddd,,,, zzzzfffffffftttt2222dddd ---- 2D Complex-to-Complex Fast Fourier Transform.
  10.  
  11. SSSSYYYYNNNNOOOOPPPPSSSSYYYYSSSS
  12.      _F_o_r_t_r_a_n :
  13.      ssssuuuubbbbrrrroooouuuuttttiiiinnnneeee ccccfffffffftttt2222dddd(((( ssssiiiiggggnnnn,,,, nnnn1111,,,, nnnn2222,,,, aaaarrrrrrrraaaayyyy,,,, llllddddaaaa,,,, ccccooooeeeeffff ))))
  14.           iiiinnnntttteeeeggggeeeerrrr            ssssiiiiggggnnnn,,,, nnnn1111,,,, nnnn2222,,,, llllddddaaaa
  15.           ccccoooommmmpppplllleeeexxxx        aaaarrrrrrrraaaayyyy((((llllddddaaaa,,,,nnnn2222)))),,,, ccccooooeeeeffff((((((((nnnn1111++++11115555))))++++((((nnnn2222++++11115555))))))))
  16.  
  17.      ssssuuuubbbbrrrroooouuuuttttiiiinnnneeee zzzzfffffffftttt2222dddd(((( ssssiiiiggggnnnn,,,, nnnn1111,,,, nnnn2222,,,, aaaarrrrrrrraaaayyyy,,,, llllddddaaaa,,,, ccccooooeeeeffff ))))
  18.           iiiinnnntttteeeeggggeeeerrrr            ssssiiiiggggnnnn,,,, nnnn1111,,,, nnnn2222,,,, llllddddaaaa
  19.           ddddoooouuuubbbblllleeee ccccoooommmmpppplllleeeexxxx  aaaarrrrrrrraaaayyyy((((llllddddaaaa,,,,nnnn2222)))),,,, ccccooooeeeeffff((((((((nnnn1111++++11115555))))++++((((nnnn2222++++11115555))))))))
  20.  
  21.  
  22.      _C :
  23.      ####iiiinnnncccclllluuuuddddeeee <<<<fffffffftttt....hhhh>>>>
  24.      iiiinnnntttt ccccfffffffftttt2222dddd (((( iiiinnnntttt ssssiiiiggggnnnn,,,, iiiinnnntttt nnnn1111,,,, iiiinnnntttt nnnn2222,,,, ccccoooommmmpppplllleeeexxxx ****aaaarrrrrrrraaaayyyy,,,,
  25.                     iiiinnnntttt llllddddaaaa,,,, ccccoooommmmpppplllleeeexxxx ****ccccooooeeeeffff))));;;;
  26.      iiiinnnntttt zzzzfffffffftttt2222dddd (((( iiiinnnntttt ssssiiiiggggnnnn,,,, iiiinnnntttt nnnn1111,,,, iiiinnnntttt nnnn2222,,,, zzzzoooommmmpppplllleeeexxxx ****aaaarrrrrrrraaaayyyy,,,,
  27.                     iiiinnnntttt llllddddaaaa,,,, zzzzoooommmmpppplllleeeexxxx ****ccccooooeeeeffff))));;;;
  28.  
  29.  
  30. DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  31.      ccccfffffffftttt2222dddd and zzzzfffffffftttt2222dddd compute in place the complex Fourier transform of
  32.      complex 2D sequence of size N1 x N2.  The value F{k,l} of the transform
  33.      of the 2D sequence f{i,j} is equal to:
  34.           F{k,l} = Sum ( W1^(i*k) * W2^(j*l) * f{i,j} ),
  35.                   for i =0,...,(N1-1), and j=0,...,(n2-1)
  36.               W1 = exp( (Sign*2*sqrt(-1)*PI) / N1 )
  37.               W2 = exp( (Sign*2*sqrt(-1)*PI) / N2 )
  38.  
  39.  
  40. SSSSttttoooorrrraaaaggggeeee
  41.      It is assumed that the (N1 x N2) 2D sequence is stored along dimension
  42.      N1.  So the index {i+1,j} has an offset of 1 element with respect to
  43.      {i,j}, and {i,j+1} an offset of _l_d_a elements with respect to {i,j}.
  44.  
  45. AAAAllllggggoooorrrriiiitttthhhhmmmm
  46.      The complex-to-complex 2D Fourier transform is computed with a row-column
  47.      approach.
  48.       - First, N2 FFTs complex-to-complex of size N1 are evaluated, stride = 1
  49.      and leading_dimension=lda.
  50.       - then, N1 FFTs complex-to-complex of size N2 are preformed, stride=lda,
  51.      and leading_dimension=1.
  52.  
  53. PPPPAAAARRRRAAAAMMMMEEEETTTTEEEERRRRSSSS
  54.      SSSSIIIIGGGGNNNN ---- Integer specifying which sign to be used for the expression of W
  55.      (see above) - must be either +1 or -1.
  56.      Unchanged on exit.
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. ccccfffffffftttt2222dddd,,,,zzzzfffffffftttt2222dddd((((3333FFFF))))                                            ccccfffffffftttt2222dddd,,,,zzzzfffffffftttt2222dddd((((3333FFFF))))
  71.  
  72.  
  73.  
  74.      NNNN1111 ---- Integer, the first dimension size of the 2D sequence.
  75.      Unchanged on exit.
  76.  
  77.      NNNN2222 ---- Integer, the second dimension size of the 2D sequence.
  78.      Unchanged on exit.
  79.  
  80.      AAAARRRRRRRRAAAAYYYY ---- Array containing the samples of the 2D sequence to be
  81.      transformed.
  82.      On input, the element {i,j} of the sequence is stored as A(i,j) in
  83.      _F_o_r_t_r_a_n , and A[i+j*lda] in _C.
  84.      On exit, the array is overwritten by its transform.  LLLLDDDDAAAA ---- Integer,
  85.      leading dimension: increment between the samples of two consecutive sub-
  86.      sequences (e.g between {i,j+1} and {i,j}).  llllddddaaaa >>>>==== NNNN1111
  87.      Unchanged on exit.
  88.  
  89.      CCCCOOOOEEEEFFFFFFFF ---- Array of at least ( (N+15)+(N2+15) ) elements.  On entry it
  90.      contains the Sines/Cosines and factorization of N. COEFF needs to be
  91.      initialized with a call to cfft2di or zfft2di. Unchanged on exit.
  92.  
  93.  
  94. EEEExxxxaaaammmmpppplllleeee ooooffff CCCCaaaalllllllliiiinnnngggg SSSSeeeeqqqquuuueeeennnncccceeee
  95.      2D FFT computed for a 64*1024 complex value sequence. The elements of
  96.      each sequence are stored with increment (stride) 1, and the offset
  97.      between the first element of two succesive sequence (leading dimension)
  98.      is 2049.
  99.      _F_o_r_t_r_a_n
  100.           complex array(0:2049-1,0:64-1), coeff(1024+15 + 64+15)
  101.           call cfft2di( 1024, 64, coeff)
  102.           call cfft2d( -1, 1024, 64, array, 2049, coeff)
  103.  
  104.      _C
  105.           #include <fft.h>
  106.           complex array[64*2049], *coeff;
  107.           coeff = cfft2di( 1024, 64, NULL);
  108.           cfft2d( -1, 1024, 64, array, 2049, coeff);
  109.  
  110. SSSSEEEEEEEE AAAALLLLSSSSOOOO
  111.      fft, cfft2di, zfft2di
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.